#每次 j 增加时，都是在之前和的基础上加上 arr[j]。因此，可以去掉内层循环，直接维护一个 current_sum，每次 j 增加时，current_sum += arr[j]，这样可以将时间复杂度从 O(n³) 优化到 O(n²)。
def max_subarray_optimized(arr):
    n = len(arr)
    max_sum = float('-inf')  # 初始化为负无穷
    best_i = best_j = -1     # 记录最佳区间的起始和结束索引

    for i in range(n):
        current_sum = 0  # 每次i变化时，重新计算从i开始的子数组和
        for j in range(i, n):
            current_sum += arr[j]  # 在上一次和的基础上加上arr[j]，避免重复计算
            if current_sum > max_sum:
                max_sum = current_sum
                best_i, best_j = i, j

    return max_sum, (best_i, best_j)

# 示例：使用10个数的实数序列
arr = [1, -2, 3, 10, -4, 7, 2, -5, -8, 6]
max_sum, (i, j) = max_subarray_optimized(arr)

print("序列:", arr)
print("最大子数组和:", max_sum)
print("最大子数组的区间: 从索引", i, "到", j)
print("最大子数组:", arr[i:j+1])
